package 数组题目.前缀和与差分;

//二维区域和检索 - 矩阵不可变
//https://leetcode.cn/problems/range-sum-query-2d-immutable/description/
class 二维前缀和 {
    int[][] matrixSum;

    public 二维前缀和(int[][] matrix) {
        int rowLen = matrix.length + 1;
        int colLen = matrix[0].length + 1;
        this.matrixSum = new int[rowLen][colLen];
        for (int i = 1; i < rowLen; i++) {
            for (int j = 1; j < colLen; j++) {
                this.matrixSum[i][j] = matrix[i - 1][j - 1] + matrixSum[i - 1][j] + matrixSum[i][j - 1] - matrixSum[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return matrixSum[row2 + 1][col2 + 1] - matrixSum[row2 + 1][col1] - matrixSum[row1][col2 + 1] + matrixSum[row1][col1];
    }

    public static void main(String[] args) {
        二维前缀和 二维前缀和 = new 二维前缀和(new int[][]{{3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5}});
        System.out.println(二维前缀和.sumRegion(2, 1, 4, 3));
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
